package com.cn.codebrush.练习;

/**
 * @Author Boolean
 * @Date 2022/6/20 16:01
 * @Version 1.0
 */
public class 背包问题 {
    public static void main(String[] args) {
        int cap =8;
        int[] weight = {2,3,4,5};
        int[] value = {3,4,5,6};
        System.out.println(heightValue(cap,weight,value));
    }

    //https://blog.csdn.net/qq_54809548/article/details/120810692
    public static   int heightValue(int cap,int[] weight,int[] value){
        int n = weight.length;
        int[][] dp = new int[n][cap+1];
        for (int i =0;i<n;i++){
            for(int j=0;j<=cap;j++){
                if(j < weight[i]){
                    if(i == 0){
                        dp[i][j] = 0;
                    }else {
                        dp[i][j] = dp[i-1][j];
                    }
                }else {
                    if(i == 0){
                        dp[i][j] = value[i];
                    }else {
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                    }

                }
            }

        }

        return dp[n-1][cap];
    }
}
